package basic.study.wantOffer.chapter5;

/**
 * @ClassName Problem55
 * @Description 二叉树的深度
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/12 19:03
 * @Version 1.0
 */
public class Problem55 {
    /**
     * 解法：BFS
     * @param node
     * @return
     */
    int findTreeDepth(Problem52.Node node) {
        if (node == null) {
            return 0;
        }
        int left = findTreeDepth(node.left);
        int right = findTreeDepth(node.right);
        return Math.max(left + 1, right + 1);
    }

    class Problem55_2 {
        /**
         * 平衡二叉树
         * 做法1：接着上面的做法
         */
        boolean isBalanced(Problem52.Node node) {
            if (node == null) {
                return true;
            }
            int left = findTreeDepth(node.left);
            int right = findTreeDepth(node.right);
            int diff = Math.abs(left - right);

            if (diff > 1) {//剪枝
                return false;
            }
            else {
                return isBalanced(node.left) && isBalanced(node.right);
            }
        }

        /**
         * 每个节点只遍历一次的做法
         */
        boolean isBalanced2(NewNode node) {
            if (node == null) {
                return true;
            }
            int left = findTreeDepth2(node.left);
            int right = findTreeDepth2(node.right);
            int diff = Math.abs(left - right);

            if (diff > 1) {//剪枝
                return false;
            }
            else {
                return isBalanced2(node.left) && isBalanced2(node.right);
            }
        }

        private int findTreeDepth2(NewNode node) {
            if (node == null) {
                return 0;
            }
            if (node.depth != -1) {
                return node.depth;
            }
            int left = findTreeDepth2(node.left);
            int right = findTreeDepth2(node.right);

            int depth =  Math.max(left + 1, right + 1);
            node.depth = depth;
            return depth;
        }
    }

    class NewNode {
        NewNode left;
        NewNode right;
        int val;
        int depth = -1;
    }
}
